package leetcode;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
/**
 * 144.二叉树的前序遍历
 * 给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
 * 输入：root = [1,null,2,3]
 * 输出：[1,2,3]
 * 输入：root = [1,null,2]
 * 输出：[1,2]
 */
public class Num_144 {
    /** 方法一：递归 **/
    List<Integer> list = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        //边界条件
        if(root == null){
            return list;
        }
        //先添加根节点
        list.add(root.val);
        //递归遍历左子树
        preorderTraversal(root.left);
        //递归遍历右子树
        preorderTraversal(root.right);
        return list;
    }

    /** 方法二：迭代,利用栈 **/
    public List<Integer> preorderTraversal2(TreeNode root){
        List<Integer> list = new ArrayList<>();
        //边界条件
        if(root == null){
            return list;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        stack.offerFirst(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pollFirst();
            //先添加根节点的值
            list.add(node.val);
            //因为栈是先进先出，所以这里先将右子树入栈，再将左子树入栈
            //出栈的时候就可以先出左子树
            if(node.right != null){
                stack.offerFirst(node.right);
            }
            if(node.left != null){
                stack.offerFirst(node.left);
            }
        }
        return list;
    }
}
